\documentclass[12pt]{article}
\usepackage{amsfonts,amssymb}
\usepackage{amsmath}
\usepackage{graphicx}

%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex
%
\input xy
\xyoption{all}

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 1\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{\{jianchan,sanjian,yeming\}@cis.upenn.edu}

\end{center}

\vspace {0.25cm}\noindent
{\bf Solution B1.}

\vspace {0.25cm}\noindent
(i) Proof:
\begin{enumerate}
 \item When $ i = 0$, the only string with length 0 is $\epsilon$. And, $\delta(q_0,\epsilon)=q_0$. Therefore,  $Q_{r}^{0} = \{q_0\}$, and $Q_{r}^{0}$ is the set of all states reachable from $q_0$ using paths of length $0$.
 \item When $ i = n$, assume that $Q_{r}^{n}$ is the set of all states reachable from $q_0$ using paths of length $n$. That is to say, given any string $w\in\Sigma^*$ of length $n$. There exists a state $q\in Q_{r}^{n}$, such that $\delta^*(p,w)=q$.
 \item When $i=n+1$, given any string $w\in\Sigma^*$ of length $n+1$, there exits string $w'$ of length $n$ $(w\in\Sigma^*)$ and symbol $a\in\Sigma$, such that $w=w^,a$. By induction hypothesis, there exists a state $q\in Q_{r}^{n}$, such that $\delta^*(p,w')=q$. According to the definition, $Q_{r}^{n+1} = \{q\in Q \mid \exists p\in Q_{r}^{n}, \exists a\in\Sigma,\> q = \delta(p,a)\}$. Then we can have that $Q_{r}^{n+1}$ is the set of all states reachable from $q_0$ using paths of length $n+1$.
\end{enumerate}
In conclusion, $Q_{r}^{i}$ is the set of all states reachable from $q_0$ using paths of length $i$.

\vspace {0.25cm}\noindent
(ii) Proof: The following DFA should serve as counter-examples for both cases:
$$D = (Q,\Sigma,\delta,q_0,F), Q=\{S_1,S_2\}, \Sigma=\{a\}, q_0=S_1, F=\{S_2\}$$
$$
\xymatrix{ S_1 \ar[r]^{a}  & \> S_2 \ar[l]^{a} \\}
$$

\vspace {0.25cm}\noindent
(iii) Proof:
\begin{itemize}

    \item Assume there does not exist such a smallest integer $i_0$. Then, according to the definition, for any $i>0$, $Q_{r}^{i+1} - Q_{r}^{i} \neq \emptyset$, and $Q_{r}^{i} \subseteq Q_{r}^{i+1}$. Therefore, when $i\rightarrow\infty$, the number of states in $Q_{r} \rightarrow\infty $. Then, it contradicts with the definition of DFA. We have $Q_{r}^{i} = Q_{r}^{i+1}$.

    \item It is trivial to say that $Q_r^{i} \subseteq Q_r$. Assume there is $q_r \in Q_r$, but $q_r \notin Q_{r}^{i}=Q_{r}^{i+1}$, with above we have $\forall j>i, Q_{r}^{i}=Q_{r}^{j}, q_r \notin Q_{r}^{j}$, and $\forall i>j, q_r \notin Q_{r}^{j} \subseteq  Q_{r}^{i} $. Then $q_r$ is not reachable, it contradicts with the assumption $q_r \in Q_r$. We conclude $Q_r^{i} = Q_r$.

\end{itemize}

\vspace {0.25cm}\noindent
$D_r$ is a DFA, since the five-tuple of $D_r$ comply with the definition of DFA.

\vspace {0.25cm}\noindent
\begin{enumerate}
    \item $(F \cap Q_r) \subseteq F$, it is trivial to show that $L(D_r) \subseteq L(D)$.
    \item Given any string $w \in L(D)$, according to definition, $p = \delta^*(q_0,w) \in F$. Following the path of symbols in string $w$, $p$ is reachable, \textit{i.e.}, $p \in Q_r$. Therefore, we can have $p \in (F \cap Q_r)$. We now have $L(D) \subseteq L(D_r)$.
\end{enumerate}
With (1)(2), we have $L(D) = L(D_r)$.

\vspace {0.25cm}\noindent
{\bf Solution B2.}

\vspace {0.25cm}\noindent
(i) Proof:
Assume string $w=uv$, the length of string $u$ is $j$, the length of string $v$ is $i$. Therefore, the length of string $w$ is $i+j$.

\begin{enumerate}
 \item When $i = 0$, $v=\epsilon$. $(uv)^R = (u\epsilon)^R = (u)^R$. According to the definition, $\epsilon^R = \epsilon$, $v^R u^R=\epsilon^R u^R=\epsilon u^R = u^R$. Therefore, $(uv)^R=v^R u^R$.

 \item When $i = 1$, $v=a$. $(uv)^R = (ua)^R $. According to the definition, $(ua)^R = a^R u^R = v^R u^R$. Therefore, $(uv)^R=v^R u^R$.

 \item When $i = n$, assume that $(uv)^R=v^R u^R$.

 \item When $i=n+1$, $v=av'$, and the length of $v'=n$. $(uv)^R = (uav')^R$. Using induction hypothesis and definition, $(uav')^R = v'^R(ua)^R = v'^Rau^R = (v'a)^Ru^R = v^Ru^R$.

\end{enumerate}
With (1)(2)(3)(4), we have $(uv)^R=v^R u^R$.

\vspace {0.25cm}\noindent
(ii) Proof:
Assume the length of string $w$ is $i$.

\begin{enumerate}
 \item When $i = 0$, $w=\epsilon$. According to the definition, $(\epsilon^R)^R = (\epsilon)^R = \epsilon$. Therefore, $(w^R)^R = w$.

 \item When $i = 1$, $w=a$. $(a^R)^R = (a)^R = a$. Therefore, $(w^R)^R = w$.

 \item When $i = n$, assume that $(w^R)^R = w$.

 \item When $i=n+1$, $w=aw'$, and the length of $w'=n$. $(w^R)^R = ((aw')^R)^R = (w'^Ra)^R = a(w'^R)^R$. Using induction hypothesis, $a(w'^R)^R = aw' = w$.

\end{enumerate}
With above, we have $(w^R)^R = w$.

\vspace {0.25cm}\noindent
{\bf Solution B3.}

\vspace {0.25cm}\noindent
Proof:
\begin{itemize}
    \item $\Leftarrow$ If $u = w^m$ and $v = w^n$, for some $m, n\geq 0$, then $uv=w^{m+n}=vu $
    \item $\Rightarrow$ If $uv=vu$
    \begin{itemize}
        \item Without loss of generality, suppose $|u| \geq |v|$, then there $\exists x,y\in \mathbb{N} \ni |u|=x\cdot|v|+y$
        \item Define an operation $\omega_0 = MOD(u,v)$ where $\omega_0,u,v$ are strings:
        \begin{enumerate}
            \item $uv = vu$ and without loss of generality, say $|u| \geq |v|$ $\Rightarrow v$ is prefix of $u$, which means $\exists |u_1| = |u| - |v| \ni u=vu_1$
            \item $u=vu_1 \land uv = vu \Rightarrow vu_1v = vvu_1 \Rightarrow u_1v =
            vu_1$, same to step 1, we have $v$ is prefix of $u_1$
            \item Repeat this process $x$ times, what we do here is
            deducting $v$ from the beginning of $u$ $x$ times.
            \item Finally we reach the step that $u_xv = vu_x$,
            noticing$|u|=x\cdot|v|+y$, so here $|u_x| = y < |v|$,
            \item Let $\omega_0 = u_x$, we say $\omega_0 = MOD(u,v)$
        \end{enumerate}
        \item As we can see, operation $\omega_0 = MOD(u,v)$ borrows some
        idea from the arithmetic operation $mod(x,y)$, in fact we have shown $|\omega_0| = mod(|u|,|v|)$. The
        difference is we are dealing with strings instead of
        numbers here. In arithmetic, we can get the $gcd$ of two
        numbers by implementing Euclid Algorithm. Similarly, we can
        do the same thing to strings $u$ and $v$, using the
        $MOD(u,v)$ operation we just defined. We will see the result is
        we get a string $|\omega| = gcd(|u|,|v|)$ which is exactly
        what we are looking for.
        \item Bases on Euclid Algorithm and $MOD$ operation, we defining
        operation \newline $\omega = GCD(u,v)$ where $\omega,u,v$ are strings:
        \begin{enumerate}
            \item Input two strings $u$ and $v$, without loss of generality, say $|u| \geq |v|$.
            \item $\omega_0 = MOD(u,v)$, $MOD$ is as we defined
            before.
            \item If $|\omega_0| \neq 0$, then let $\omega_1 = MOD(v,\omega_0)$
            \item If $|\omega_1| \neq 0$, then let $\omega_2 = MOD(\omega_0, \omega_1)$
            \item ...
            \item Noting that $MOD$ operation holds property that if $\omega_0 = MOD(u,v)$, then $|\omega_0| = mod(|u|,|v|)$.
            According to Euclid Algorithm, after finite steps, we
            will reach $\omega_n = MOD(\omega_{n-2}, \omega_{n-1})$ and
            $|\omega_n| = 0$, then $|\omega_{n-1}| = gcd(|u|,|v|)$.
            \item Let $\omega = \omega_{n-1}$
        \end{enumerate}
        \item Here we found an $\omega = MOD(u,v)\ni |\omega| =
        gcd(|u|,|v|)|$, next we proof that this $\omega$ is what we
        are looking for, which means $u = \omega^m \land v =
        \omega^n$, for doing this, we go through $GCD$ operation
        inversely:
        \begin{enumerate}
            \item From the last step of $GCD$, we know $\omega_n = MOD(\omega_{n-2}, \omega)$ and
            $|\omega_n| = 0$, so $\omega_{n-2} = \omega^x$.
            \item $\omega = MOD(\omega_{n-3}, \omega_{n-2}) \land \omega_{n-2} =
            \omega^x$, it is easy to show by definition of $MOD$
            operation that $\omega_{n-3} = \omega^y$
            \item Repeat this process and noting that we started
            from $u$ and $v$, finally we have $u = \omega^m \land v = \omega^n$
        \end{enumerate}
        \item Hence, we proof that the string $\omega$ we get from
        $\omega = MOD(u,v)$ holds the property that $u = \omega^m \land v =
        \omega^n$, which means if $uv = vu$ there is some $\omega
        \in \Sigma^{star}$ such that $u = \omega^m$ and $v =
        \omega^n$.
    \end{itemize}
    \item With $\Leftarrow$ and $\Rightarrow$, we show that for any two strings $u, v\in\Sigma^*$, $uv = vu$ iff there is some $w\in\Sigma^*$ such that $u = w^m$ and $v = w^n$, for some $m, n\geq 0$.
\end{itemize}

\vspace{0.25cm}
\noindent
{\bf Solution B4.}

\vspace{0.25cm}
\noindent
(a)(i) Proof:
\begin{itemize}
    \item Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, $D_3 = (Q_3,\Sigma,\delta_3,q_{03},F_3)$. Since $f,g$ are both morphism, we have $f(q_{01})=q_{02}, g(q_{02})=q_{03}$, and $g \circ f(q_{01}) = q_{03}$. For any states $q_1, q_2, q_3$ belong to $D_1, D_2, D_3$ respectively, $f(q_1)=q_2, g(q_2)=q_3$, and $\delta_1(q_1, a) = q'_1, \delta_2(q_2, a) = q'_2, \delta_3(q_3, a) = q'_3$, then we have $g \circ f( \delta(q_{1}, a) ) = q'_3$. We conclude that $g \circ f$ is also a morphism.
  \item Since $f(F_1) \subseteq F_2$, and $g(F_2) \subseteq F_3$, $g \circ f(F_1)=g(f(F1)) \subseteq F_3$. Similarly, $f^{-1}(F_2) \subseteq F_1$, and $g^{-1}(F_3) \subseteq F_2$, ${g \circ f}^{-1}(F_3)=f^{-1}(g^{-1}(F3)) \subseteq F_1$.
\end{itemize}
With above, $\mapdef{g\circ f}{D_1}{D_3}$ is also a morphism (resp. $F$-map, resp $F^{-1}$-map) of DFAs.

\vspace{0.25cm}
\noindent
(a)(ii) Proof:
\begin{itemize}
    \item If $\mapdef{f}{D_1}{D_2}$ is an $F$-map, since it is an isomorphism, by definition we have that: there is a $F$-map $\mapdef{g}{D_2}{D_1}$ so that $g(F_2) \subseteq F_1$. According to the definition, $g$ is unique and it is denoted $f^{-1}$, then we have $f$ is also an $F^{-1}$-map.
    \item Similarly, if $\mapdef{f}{D_1}{D_2}$ is an $F^{-1}$-map, since it is an isomorphism, by definition we have that: there is a $F^{-1}$-map $ \mapdef{g}{D_2}{D_1}$ so that $g^{-1}(F_1) \subseteq F_2$. According to the definition, $g^{-1}$ is unique and it is denoted $f$, then we have $f$ is also an $F$-map.
\end{itemize}

\vspace{0.25cm}
\noindent
(b) Proof:
Assume the length of string $w$ is $i$.
\begin{enumerate}
 \item When $i = 1$, $w=a$. According to the definition, $h(\delta_1^*(p, w)) = h(\delta_1(p, a)) = \delta_2(h(p),a) = \delta_2^*(h(p),a) = \delta_2^*(h(p),w)$.

 \item When $i = n$, assume that $h(\delta_1^*(p, w)) = \delta_2^*(h(p),w)$.

 \item When $i=n+1$, $w=aw'$, and the length of string $w'$ is $n$. Then we have:
    $$h(\delta_1^*(p, w)) = h(\delta_1^*(p, aw')) = h( \delta_1^*(\delta_1^*(p, a), w'))$$
    Using induction hypothesis:
  $$h( \delta_1^*(\delta_1^*(p, a), w')) = \delta_2^*(h(\delta_1^*(p, a)),w') = \delta_2^*(\delta_2(h(p),a),w') = \delta_2^*(h(p),aw') = \delta_2^*(h(p),w)$$
\end{enumerate}
With (1)(2)(3), we have $h(\delta_1^*(p, w)) = \delta_2^*(h(p),w)$.

\vspace{0.25cm}
\noindent
As a consequence,
\begin{itemize}
    \item For all strings $w$, which $\delta_1^*(q_{0,1},w) \subseteq F_1 $. Since $\mapdef{h}{D_1}{D_2}$  is an $F$-map of DFA's, then $h(\delta_1^*(q_{0,1},w)) = \delta_2^*(h(q_{0,1}),w) = \delta_2^*(q_{0,2},w) \subseteq F_2$. Then we have $L(D_1) \subseteq L(D_2)$.
    \item Similarly, for all strings $w$, which $ \delta_2^*(q_{0,1},w) \subseteq F_2 $. Since $\mapdef{h}{D_1}{D_2}$  is an $F^{-1}$-map of DFA's, then $h(\delta_2^*(q_{0,2},w)) = \delta_1^*(h(q_{0,2}),w) = \delta_1^*(q_{0,1},w) \subseteq F_1$. Then we have $L(D_2) \subseteq L(D_1)$.
    \item For proper homomorphism of DFA's, with above, it is trivial to show that $L(D_1) = L(D_2)$.
\end{itemize}

\vspace{0.25cm} \noindent
 (c) Proof:
\begin{enumerate}
  \item Unique: We firstly prove that, if $\exists p\in (D_1)_r$ so that $h(p)\neq
  h'(p)$, then we can find $q,p\in (D_1)_r$ so that
  $\delta_1(q,a)=p$, where $a\in \Sigma$, $h(q)=h'(q)$ and $h(p)\neq
  h'(p)$. By definition of morphism, we have
  $h(p_{0,1})=h'(p_{0,1}) = p_{0,2}$.
  \vspace{.25cm}

  Suppose $p\in (D_1)_r$ so that $h(p)\neq h'(p)$, since all
  elements $\in (D_1)_r,(D_2)_r$ are reachable from
  $p_{0,1},p_{0,2}$, there must be two different paths from
  $p_{0,2}$ to $h(p)$ and $h'(p)$. Denote the last state $\in
  (D_2)_r$ where the two paths meet as $h(q)=h'(q)$, then the next
  states are $h(p)\neq h'(p)$. Here $p,q\in (D_1)_r$ are the states
  meeting the above requirements.
  \vspace{0.25cm}

  From the definition of morphism we have $h(p)=\delta_2(h(q),a)$
  and $h'(p)=\delta_2(h'(q),a)$. Since $h(q)=h'(q)$, so we have
  $h'(p)=\delta_2(h(q),a)$. Since $h(p)\neq h'(p)$, this means
  $\delta_2(h(q),a)$ has two different values, which contradicts the
  deterministic property of DFA. So $\forall p\in (D_1)_r, h(p) =
  h'(p)$.
  \item Surjective: Suppose surjective property is not met, that is
  $\exists x\in (D_2)_r$ so that $\forall p\in (D_1)_r, h(p)\neq x.$
  By definition of morphism we have $h(p_{0,1})=p_{0,2}$, so we can
  find $y,x\in (D_2)_r$ that, $\exists q\in (D_1)_r$ that $h(q)=y$
  but $\forall p\in (D_1)_r$ that $h(p)\neq x$.
  \vspace{0.25cm}

  Since $D_2$ is DFA, suppose $a\in \Sigma$ that $\delta_2(y,a)=x$.
  Denote $p\in (D_1)_r$ so that $p=\delta_1(q,a)$, then $h(p)\neq
  x$. By the definition of morphism, $\exists z\in (D_2)_r$ so that
  $z=h(p)$. Since $h(\delta_1(q,a))=\delta_2(h(q),a)$, so that
  $h(p)=\delta_2(y,a)=z$. Here we have $\delta_2(y,a)=x=z$, but
  $x\neq h(p)=z, x\neq z$, this means $\delta_2(y,a)$ has two values, which contradicts with the deterministic property
  of DFA. So $\mapdef{h}{D_1}{D_2}$ is surjective.

  \item Homomorphism: We firstly prove that $\forall f_1\in (F_1)_r,
  \exists f_2\in (F_2)_r$ so that $h(f_1)=f_2$. Suppose not, then
  $\exists p_2\in (D_2)_r$ while $p_2$ not $\in (F_2)_r$ that
  $h(f_1)=p_2$.
  \vspace{0.25cm}

  Denote $w\in \Sigma^*$ that $\delta_1^*(p_{0,1},w)=f_1$. Since
  $h(p_{0,1})=p_{0,2}$ and $h(f_1)=p_2$, so that
  $\delta_2^*(p_{0,2},w)=p_2$. Due to the deterministic property of
  $D_2$, $\delta_2^*(p_{0,2},w)$ has only one value $p_2$. Since
  $p_2$ not $\in (F_2)_r$, so $w$ not $\in L(D_2)$. This contradicts
  with $L(D_1)=L(D_2)$.
  \vspace{0.25cm}

  In the same way, $\forall f_2\in (D_2)_r, \exists f_1\in (D_1)_r$
  that $h(f_1)=f_2$. In sum, we have $h^{-1}((F_2)_r)=(F_1)_r$. So
  $h$ induces a proper homomorphism $\mapdef{h'}{(D_1)_r}{(D_2)_r}$.
  Note that $h'$ is also unique and surjective from the proof above.
\end{enumerate}
(d) Proof:
\begin{enumerate}
  \item When $h$ is a weak $F-map$, denote $p\in D_2=h(q_{0,1})$,
  and $u$ is a string over $\Sigma$ that $\delta_2^*(q_{0,2},u)=p$.
  $\forall w\in L(D_1)$, since h is a weak $F-map$, we have
  $\delta_2^*(p,w)\in F_2$, and then $\delta_2^*(q_{0,2},uw)\in
  F_2$. So $uw\in L(D_2), w\in D_u(L(D_2))$. That is $\forall w\in
  D(L_1), w\in D_u(L(D_2))$. So we have $L(D_1)\subseteq D_u(L(D_2))$.

  \item When $h$ is a weak $F^{-1}-map$, denote $p\in D_2=h(q_{0,1})$,
  and $u$ is a string over $\Sigma$ that $\delta_2^*(q_{0,2},u)=p$.
  $\forall uw\in L(D_2))$, since h is a weak $F^{-1}-map$, we have
  $h^{-1}(\delta_2^*(q_{0,2},uw))=\delta_1^*(q_{0,1},w)$, so that
  $w\in L(D_1)$. Since $w\in D_u(L(D_2))$, that is $\forall w\in
  D_u(L(D_2))$, $w\in L(D_1))$. So we have $D_u(L(D_2))\subseteq
  L(D_1)$.

  \item $\forall w\in L(D_1)$, by definition of homomorphism and the
  analysis above, we have $\delta_2^*(q_{0,2},uw)\in F_2$, that is
  $uw\in L(D_2))$, so $w\in D_u(L(D_2))$.

  $\forall uw\in L(D_2)$, in the same way, we have
  $\delta_1^*(q_{0,1},w)\in F_1$, that is $w\in L(D_1)$. In sum, we
  have $L(D_1)=D_u(L(D_2))$.

  \item If $h$ is a weak morphism, $h$ may not be unique from
  $(D_1)_r$ to $D_2$. This can be shown when $D_2$ contains some
  unreachable state groups, each of which is the same as $(D_1)_r$.
  In such situation, $(D_1)_r$ can match any such group, making $h$
  not unique.

  If $h(q_{0,1})\neq q_{0,2}$, then $h$ is not surjective. The
  states in $D_2$ which are previous to $h(q_{0,1})$ don't have
  matching states in $D_1$.

  Further, when $D_2$ is not trim, h is not unique and not surjective.
\end{enumerate}

\vspace{0.25cm} \noindent
\noindent
{\bf Solution B5}

\vspace{0.25cm} \noindent
(a)(i) Proof:
If $L = \{\epsilon\}$, it is easy to show $S = \{\epsilon\}$, $S \subseteq L$, and $L = S^*$.
Else,
\begin{itemize}
    \item Firstly, let $\epsilon \in S$. Assume $L$ contains $n+1$ strings $(n\geq0)$, namely: $L=\{\epsilon, a^{m_1}, \cdots , a^{m_n}\}$, and $(m_1 \leq m_2 \leq \cdots \leq m_n)$. Then we can classify each string $a^m \in L$ into one of the ${m_1}$ congruence classes, according to the remainder of $m/m_1$. If the $ith$ congruence class is not empty, then let the string $a^{m_i}$, which ${m_i}$ is the smallest number in the ith congruence class, belongs to $S$. According to this construction of $S$, we can see $S$ is a finite set. For any string $a^m \in L$, assume $a^m$ belongs to the $ith$ congruence class, it is trivial to show that there exists $p \in Z$, $a^m = a^{m_i+p*m_1}$. That is to say, $L \subseteq S^*$.
    \item Since $S \subseteq L$, then $S^* \subseteq L^* = L$. We have $S^* \subseteq L$.
\end{itemize}
With above, we complete the proof.

\vspace{0.25cm} \noindent
(a)(ii) Proof:
\begin{enumerate}
    \item It is easy to construct a set of NFA $N_s$ to accept each string in $S$.
    \item Add a new start state, a new final state, and necessary transition with $\epsilon$. It is easy to combine all the NFA in $N_s$, and get a single NFA $N_S$, with its language equals to $S$.
    \item Add transition with $\epsilon$ from the new final state to the new start state, then we have the NFA $N_{S^*}$, with its language equals to $S^*$.
    \item Convert the NFA $N_{S^*}$ to DFA.
\end{enumerate}
Following the steps above, we have a DFA with its language equals to $L$, then $L$ is regular.

\vspace{0.25cm}
\noindent(b) Proof: If $L$ is a regular language, then it can be accepted by a
certain DFA, denoted as $D$. Since $\Sigma=\{a\}$ with the
deterministic property of DFA, there can only be one circle in $D$,
and its general state is showed in Figure \ref{fig_B5}. Suppose we have $m$
states before the circle with $q$ states. Let $F$ be the set of
final states in first m states. Further more, if $jth$ state in the
circle is final, then there is $p_i=j$. Suppose there are $k$ final
states in the circle, so we have $k$ values of $p_i(1\leq i\leq k)$.
Since each circle represents $q$ a's in a string, so $\{a^q\}^*$ can
represent any number of circles in a string. Here
$\bigcup_{i=1}^ka^{m+p_i}$ can represent the final states in the
circle. Together with set $F$, we can have
$L=F\cup\bigcup_{i=1}^ka^{m+p_i}\{a^q\}^*$.

\begin{figure}[h]
\begin{center}
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.7\linewidth]{fig}
  \caption{DFA:$D$}\label{fig_B5}
\end{center}
\end{figure}

\noindent
{\bf Solution B6}

\vspace{0.25cm}
\noindent
(a)(i) Proof:
Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, and $D = (Q_D,\Sigma,\delta_D,q_{0D},F_D)$.
Construct $D, \pi_1, \pi_2$, as follows:
\begin{itemize}
    \item $Q_D = Q_1 \times Q_2$, $q_{0D}=(q_{01},q_{02})$, $F_D=\{(q_1,q_2)\ |\ \exists q_1 \in F_1 \ or \ \exists q_2 \in F_2\}$, $\delta_D((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.
    \item $\forall (q_1,q_2) \in D$, $\pi_1((q_1,q_2)) = q_1$, $\pi_2((q_1,q_2)) = q_2$.
\end{itemize}

As we can see
\begin{itemize}
    \item  $\pi_1(q_{0D}) = q_{01}$, $\pi_2(q_{0D}) = q_{02}$, and for any $q_D=(q_1,q_2) \in Q_D$, $\pi_1( \delta_D(q_D,a) )= \pi_1( ( \delta_1(q_1,a) , \delta_2(q_1,a) ) ) = \delta_1(q_1,a) = \delta_1( \pi_1( q_D), a ) $.
    \item For al string $w$ belonging to the language of $D_1$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_2) \in F_D$.
\end{itemize}
Then we have $\pi_1$ is a $F^{-1}$ map. Similarly, $\pi_2$ is also a $F^{-1}$ map.

\medskip
For any given DFA $M= (Q_M,\Sigma,\delta_M,q_{0M},F_M)$ and any two DFA $F^{-1}$-maps $\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, assume $q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, and $g(q_M)=q_2 \in Q_2$, then we define $\mapdef{h}{M}{D}$, $h(q_M) = (q_1,q_2) \in Q_D$.

As we can see
\begin{itemize}
    \item  $h(q_{0M}) = (q_{01},q_{02}) = q_{0D}$, and for any $q_{M1} \in Q_M$, assume $\delta_M(q_{M1},a) = q_{M2}$, $h( q_{M1} ) = (q_{11},q_{21})$, $h( q_{M2} ) = (q_{12},q_{22})$. Since, $f$ and $g$ are morphism, then we have $\delta_1(q_{11},a) = q_{12}$, $\delta_2(q_{21},a) = q_{22}$. Then $ h( \delta_M( q_{M1} , a) )= h( q_{M2} ) = (q_{12},q_{22}) = \delta_M( h(q_{M2}) , a ) $.

    \item For any string $w$ belonging to the language of $D$, according to our construction, it must belong to either $D_1$ or $D_2$. Since $f,g$ are both $F^{-1}$-map, so $w$ must also belongs to the language of $M$.
\end{itemize}
Then we have $h$ is a $F^{-1}$ map.

Supposing there is another $F^{-1}$ map $h'$, $ \forall q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, $g(q_M)=q_2 \in Q_2$. According to our construction of $\pi_1$, $\pi_2$, we must have $h'(q_M)=(q_1,q_2)$. That is to say, $h$ is unique. Slimilarly, we can have $f= \pi_1 \circ h$, $g= \pi_2 \circ h$.

\vspace{0.25cm}
\noindent
(a)(ii) Proof:
From the construction of $\pi_1$, $\pi_2$, it is trivial to prove that they are surjective.
Assume DFA $D'$ is another DFA which holds the property, then there is a $F^{-1}$ map $\mapdef{\varphi'}{D'}{D}$. We also know that $D$ hold the property, then there is a $F^{-1}$ map $\mapdef{\varphi}{D}{D'}$. According to the definition, $D$ is unique up to a DFA $F^{-1}$-map isomorphism.
The language accepted by $D$ is the union of the language of $D_1$ and the language of $D_2$.


\vspace{0.25cm}
\noindent
(b)(i) Proof:
Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, $D_3 = (Q_3,\Sigma,\delta_3,q_{03},F_3)$, and $D = (Q_D,\Sigma,\delta_D,q_{0D},F_D)$.
Let $Q_{D'}= \{(q_1,q_2)\ | \ (\exists q_3 \in Q_3, f(q_1)=q(q_2)=q_3) \}$, construct $D, \pi_1, \pi_2$, as follows:
\begin{itemize}

\item $ Q_D = \{ (q_1,q_2) |  (\exists (q_1,q_2) \in Q_{D'} ) \& ( \forall a \in \Sigma  , ( \delta_1 ( f (q_1),a ) , \delta_2 (g(q_2),a) ) \in Q_{D'}) \}$, $q_{0D}=(q_{01},q_{02})$, $F_D=\{(q_1,q_2)\ |\ \exists q_1 \in F_1 \ or \ \exists q_2 \in F_2\}$, $\delta_D((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.

\item $\forall (q_1,q_2) \in D$, $\pi_1((q_1,q_2)) = q_1$, $\pi_2((q_1,q_2)) = q_2$.

\end{itemize}

As we can see
\begin{itemize}
    \item  $\pi_1(q_{0D}) = q_{01}$, $\pi_2(q_{0D}) = q_{02}$, and for any $q_D=(q_1,q_2) \in Q_D$, $\pi_1( \delta_D(q_D,a) )= \pi_1( ( \delta_1(q_1,a) , \delta_2(q_1,a) ) ) = \delta_1(q_1,a) = \delta_1( \pi_1( q_D), a ) $.
    \item For any string $w$ belonging to the language of $D_1$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_2) \in F_D$.
\end{itemize}
Then we have $\pi_1$ is a $F^{-1}$ map. Similarly, $\pi_2$ is also a $F^{-1}$ map.

\medskip
For any given DFA $M= (Q_M,\Sigma,\delta_M,q_{0M},F_M)$ and any two DFA $F^{-1}$-maps $\mapdef{f'}{M}{D_1}$ and $\mapdef{g'}{M}{D_2}$, assume $q_M \in Q_M$, $f'(q_M)=q_1 \in Q_1$, and $g'(q_M)=q_2 \in Q_2$, then we define $\mapdef{h}{M}{D}$, $h(q_M) = (q_1,q_2)$ $(q_1,q_2)$ must belongs to  $Q_D$, else it contradict with the fact that $f\circ f' = g\circ g'$.

As we can see
\begin{itemize}
    \item  $h(q_{0M}) = (q_{01},q_{02}) = q_{0D}$, and for any $q_{M1} \in Q_M$, assume $\delta_M(q_{M1},a) = q_{M2}$, $h( q_{M1} ) = (q_{11},q_{21})$, $h( q_{M2} ) = (q_{12},q_{22})$. Since, $f'$ and $g'$ are morphism, then we have $\delta_1(q_{11},a) = q_{12}$, $\delta_2(q_{21},a) = q_{22}$. Then $ h( \delta_M( q_{M1} , a) )= h( q_{M2} ) = (q_{12},q_{22}) = \delta_M( h(q_{M2}) , a ) $.

    \item For any string $w$ belonging to the language of $D$, according to our construction, it must belong to either $D_1$ or $D_2$. Since $f,g$ are both $F^{-1}$-map, so $w$ must also belongs to the language of $M$.
\end{itemize}
Then we have $h$ is a $F^{-1}$ map.

Supposing there is another $F^{-1}$ map $h'$, $ \forall q_M \in Q_M$, $f'(q_M)=q_1 \in Q_1$, $g'(q_M)=q_2 \in Q_2$. According to our construction of $\pi_1$, $\pi_2$, we must have $h'(q_M)=(q_1,q_2)$. That is to say, $h$ is unique.

\vspace{0.25cm}
\noindent
(b)(ii) Proof:
Assume DFA $D'$ is another DFA which holds the property, then there is a $F^{-1}$ map $\mapdef{\varphi'}{D'}{D}$. We also know that $D$ hold the property, then there is a $F^{-1}$ map $\mapdef{\varphi}{D}{D'}$. According to the definition, $D$ is unique up to a DFA $F^{-1}$-map isomorphism.

\vspace{0.25cm}
\noindent
(b)(iii) Proof:
For the construction of $D$, $D'$, $\pi_1$, $\pi_2$, it is easy to see that when $D_3=T$, $Q_D = Q_{D'}$, then $D$ and $D'$ are identical according to the five turple definition.

\vspace{0.25cm}
\noindent
{\bf Solution Extra Credit}\\
To be concise, we only proof the part affected by the change from $F^{-1}$-map to $F$-map.

\vspace{0.25cm}
\noindent
(a)(i) Proof:
Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, and $D = (Q_D,\Sigma,\delta_D,q_{0D},F_D)$.
Construct $D, \pi_1, \pi_2$, as follows:
\begin{itemize}
    \item $Q_D = Q_1 \times Q_1$, $q_{0D}=(q_{01},q_{02})$, $F_D=\{(q_1,q_2)\ |\ \exists q_1 \in F_1 \ and \ \exists q_2 \in F_2\}$, $\delta_D((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.
    \item $\forall (q_1,q_2) \in D$, $\pi_1((q_1,q_2)) = q_1$, $\pi_2((q_1,q_2)) = q_2$.
\end{itemize}

\medskip
As we can see, for all string $w$ belonging to the language of $D$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_{1F}) \in F_D$. Since $\pi_1, \pi_2$ are morphism, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_2(q_{02},w)=q_{2F} \in F_2$. Then we have $\pi_1$ is a $F$-map. Similarly, $\pi_2$ is also a $F$-map.

\medskip
For any given DFA $M= (Q_M,\Sigma,\delta_M,q_{0M},F_M)$ and any two DFA $F$-maps $\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, assume $q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, and $g(q_M)=q_2 \in Q_2$, then we define $\mapdef{h}{M}{D}$, $h(q_M) = (q_1,q_2) \in Q_D$.

As we can see, for any string $w$ belonging to the language of $M$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_2(q_{02},w)=q_{2F} \in F_2$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_{2F}) \in F_D$.

Then we have $h$ is a $F$-map.

\vspace{0.25cm}
\noindent
(a)(ii) Proof:
Assume DFA $D'$ is another DFA which holds the property, then there is a $F$-map $\mapdef{\varphi'}{D'}{D}$. We also know that $D$ hold the property, then there is a $F$-map $\mapdef{\varphi}{D}{D'}$. According to the definition, $D$ is unique up to a DFA $F$-map isomorphism.
The language accepted by $D$ is the intersection of the language of $D_1$ and the language of $D_2$.


\vspace{0.25cm}
\noindent
(b)(i) Proof:
Let $D_1 = (Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2 = (Q_2,\Sigma,\delta_2,q_{02},F_2)$, $D_3 = (Q_3,\Sigma,\delta_3,q_{03},F_3)$, and $D = (Q_D,\Sigma,\delta_D,q_{0D},F_D)$.
Let $Q_{D'}= \{(q_1,q_2)\ | \ (\exists q_3 \in Q_3, f(q_1)=q(q_2)=q_3) \}$, construct $D, \pi_1, \pi_2$, as follows:
\begin{itemize}

\item $ Q_D = \{ (q_1,q_2) |  (\exists (q_1,q_2) \in Q_{D'} ) \& ( \forall a \in \Sigma  , ( \delta_1 ( f (q_1),a ) , \delta_2 (g(q_2),a) ) \in Q_{D'}) \}$, $q_{0D}=(q_{01},q_{02})$, $F_D=\{(q_1,q_2)\ |\ \exists q_1 \in F_1 \ and \ \exists q_2 \in F_2\}$, $\delta_D((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.

\item $\forall (q_1,q_2) \in D$, $\pi_1((q_1,q_2)) = q_1$, $\pi_2((q_1,q_2)) = q_2$.

\end{itemize}

\medskip
As we can see, for all string $w$ belonging to the language of $D$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_{1F}) \in F_D$. Since $\pi_1, \pi_2$ are morphism, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_2(q_{02},w)=q_{2F} \in F_2$. Then we have $\pi_1$ is a $F$-map. Similarly, $\pi_2$ is also a $F$-map.

\medskip
For any given DFA $M= (Q_M,\Sigma,\delta_M,q_{0M},F_M)$ and any two DFA $F$-maps $\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, assume $q_M \in Q_M$, $f(q_M)=q_1 \in Q_1$, and $g(q_M)=q_2 \in Q_2$, then we define $\mapdef{h}{M}{D}$, $h(q_M) = (q_1,q_2) \in Q_D$.

As we can see, for any string $w$ belonging to the language of $M$, $\delta^*_1(q_{01},w)=q_{1F} \in F_1$, $\delta^*_2(q_{02},w)=q_{2F} \in F_2$, $\delta^*_D(q_{0D}, w)=(q_{1F}, q_{2F}) \in F_D$.

Then we have $h$ is a $F$-map.

\vspace{0.25cm}
\noindent
(b)(ii) Proof:
Assume DFA $D'$ is another DFA which holds the property, then there is a $F$-map $\mapdef{\varphi'}{D'}{D}$. We also know that $D$ hold the property, then there is a $F$-map $\mapdef{\varphi}{D}{D'}$. According to the definition, $D$ is unique up to a DFA $F$-map isomorphism.

\end{document}
